This invention is generally related to digital image processing and more particularly to methodologies for warping an input image using affine and perspective transformations.
A digital image is an electronic representation of a scene using a collection of picture elements (xe2x80x9cpixelsxe2x80x9d). In a two-dimensional (2-D) image, each pixel may be identified by a pair of numbers or xe2x80x9ccoordinatesxe2x80x9d written in the form (u,v) of a Cartesian coordinate system, and is assigned one or more intensity values for one or more colors (abbreviated here as xe2x80x9ccolor valuesxe2x80x9d).
Spatial transformations, also referred to as warping, can transform an input, 2-D image into an output image, by scaling upwards or downwards, rotating, translating (moving), and/or shearing the input image. These transformations are known as affine transformations. Another type of spatial transform is a perspective transformation in which the image is transformed so that its edges converge to one or both axes of the output image""s coordinate system.
Image warping is used to enhance image quality and correct images in a variety of different applications, including computer graphics, computer vision, medical imaging, and remote sensing. In addition, image-based modeling and rendering (IBMR), where three-dimensional (3-D) images are created from 2D images or photographs, makes extensive use of 2-D warping to transform several reference images and then composite them for a desired 3-D view. The use of IBMR in 3-D video applications, such as computer games and computer-animation, calls for fast warping, due to the fast image rendering required for depicting complex and rapidly changing scenes.
Warping may be viewed as a mapping of the input image coordinate system (u,v) into the coordinate system (x,y) of the output image. This may be depicted by a matrix equation [xxe2x80x2,yxe2x80x2,w]T=matrixW *[u,v,1]T in which the coordinates (u,v) of a pixel in the input image are mapped to coordinates (x=xxe2x80x2/w,y=yxe2x80x2/w) by performing the matrix multiply operation and a perspective divide. The matrix W is a 3xc3x973 matrix known as a concatenated warping matrix whose elements define the affine and perspective transformations.
Some scanline warping methodologies have been developed that operate only along rows and columns of the input image and one or more intermediate images, to exploit simplifications in digital filtering and memory access. See e.g. Catmull, Edwin and Alvy Ray Smith, xe2x80x9c3-D Transformations of Images in Scanline Order,xe2x80x9d Computer Graphics, (SIGGRAPH ""80 Proceedings), vol. 14, no. 3, pp. 279-285, July 1980. The latter is a xe2x80x9ctwo-passxe2x80x9d technique in which the first pass through the input image applies a transform to each row to yield an intermediate result, and then a second pass applies another transform to each column of the intermediate result image to yield the output image.
Some of the problems with the two-pass technique referred to above include the provision of a special case for rotations of 90 degrees (due to a singularity in the transform applied in the first pass). This makes the technique more complicated in a hardware-only implementation. In addition, the two passes through the input and intermediate images may not be the most efficient way to utilize hardware parallelism. Finally, reconstruction of aliasing holes require yet another pass through the output image, thereby further increasing the time needed to warp the input image.